#include "LinkList.h"


LinkList::LinkList():size(0)
{
    //头结点：不放置有效数据，为了变成方便存在的结点
    head = new Node(0);
}


//插入
void LinkList::InsertHead(const ElementType &element)
{
    Node *newNode= new Node(element);
    newNode->next= head->next;
    head->next= newNode;
    size++;
}

void LinkList::InsertByIndex(int index, const ElementType element)
{
    //从头节点开始数index，最终停在index-1节点上
    Node *travelPoint= head;
    for(int i=0; i<index; i++)
    {
        travelPoint= travelPoint->next;
    }
    Node *newNode= new Node(element);
    newNode->next= travelPoint->next;
    travelPoint->next= newNode;
    size++;
}

void LinkList::InsertTail(const ElementType &element)
{
    //遍历指针
    Node *travelPoint = head;
    while(travelPoint->next != nullptr)
    {
        travelPoint = travelPoint->next;
    }

    travelPoint->next= new Node(element); //两句合一句
    size++;
    //int *p= new int(10); //初始化
}


//删除
void LinkList::RemoveByIndex(int index)
{
    if(index<0||index>=size)
    {
        std::cout<<"非法的删除位置"<<std::endl;
        return;
    }
    Node *travelPoint= head;
    for(int i=0; i<index; i++)
    {
        travelPoint= travelPoint->next;
    }
    Node *freeNode= travelPoint->next;

    travelPoint->next=freeNode->next;
    delete freeNode;
    size--;
}

void LinkList::RemoveByElement(const ElementType &element)
{
    Node *travelPoint= head;
    while(travelPoint->next != nullptr)
    {
        if(travelPoint->next->data== element)
        {
            Node *freeNode= travelPoint->next;
            travelPoint->next=freeNode->next;
            delete freeNode;
            size--;
        }
        else
            travelPoint= travelPoint->next;
    }

}


//查找
LinkList::ElementType *LinkList::FindByIndex(int index)
{
    if(index<0||index>=size)
    {
        std::cout<<"非法的查找位置"<<std::endl;
        return nullptr;
    }
    Node *travelPoint= head;
    for(int i=0; i<=index; i++)
    {
        travelPoint= travelPoint->next;
    }
    return &travelPoint->data;
}

DynamicArray LinkList::FindByElement(const ElementType &element)
{
    Node *travelPoint= head->next;
    DynamicArray result;
    while(travelPoint != nullptr)
    {
        if(travelPoint->data== element)
        {
            result.InsertTail(&travelPoint->data);
        }
        travelPoint= travelPoint->next;
    }
    return result;
}


//排序
//冒泡排序
void LinkList::BubbleSort()
{
    for(int i=0; i<size-1; i++)
    {
        Node *travelPoint= head; //每一次都从开始扫描链表
        for(int j=0; j<size-i-1; j++)
        {
            if(travelPoint->next->data > travelPoint->next->next->data)
            {
                Node *preNode= travelPoint->next; //前一个结点
                Node *backNode= preNode->next; //后一个结点
                preNode->next= backNode->next;
                backNode->next= preNode;
                travelPoint->next= backNode;
            }
            travelPoint= travelPoint->next;
        }
    }
}

void LinkList::Sort()
{
    FastSort(head->next,nullptr);
}

void LinkList::Reserve()
{
    Node *prev=nullptr;
    Node *cur=head->next;
    Node *back=cur->next;
    while(back!= nullptr)
    {
        cur->next= prev; //逆序
        //依次往后走
        prev= cur;
        cur= back;
        back= cur->next;
    }
    cur->next= prev; //最后一个节点要单独逆序
    head->next= cur; //新的链表头给到head的next
}

void LinkList::Reserve2()
{
    head->next= Reserve2(head->next);
}

// 显示
void LinkList::show()
{
    std::cout<<"size:"<<size<<std::endl;
    //遍历指针
    Node *travelPoint = head->next;
    while(travelPoint != nullptr)
    {
        std::cout<<travelPoint->data<<" ";
        travelPoint= travelPoint->next;
    }
    std::cout<<std::endl;
}

LinkList::~LinkList()
{
    //链表不能回头
    while(head != nullptr)
    {
        Node *nextNode= head->next; //记下下一个节点
        delete head;
        head= nextNode; //结点往后走
    }
}


//双指针：快慢指针
void LinkList::FastSort(Node *start, Node *end)
{
    if(start== end)
        return;
    Node *temp= start;  //基准值指针
    Node *slow= start;  //慢指针
    Node *fast=slow->next; //快指针
    while(fast!= end) //不走到末尾
    {
        if(fast->data<temp->data)
        {
            slow= slow->next;
            std::swap(slow->data, fast->data);
        }
        fast= fast->next;
    }
    std::swap(slow->data, temp->data);
    //递归
    FastSort(start,slow);
    FastSort(slow->next,end);
}

LinkList::Node *LinkList::Reserve2(Node *node)
{
    if(node->next== nullptr)
        return node; //返回原来的尾巴，逆序之后链表的头
    else
    {
        Node* newHead= Reserve2(node->next);
        node->next->next= node; //逆序
        node->next= nullptr; //新最后一个节点要指向空
        return newHead;
    }
}
